#!/usr/bin/python
# -*- coding: utf-8 -*-

# External imports
import sys

# Internal imports


class AnalysisError(Exception):
  pass


def correlationFactor(message, alphabet, sortedAlphabet):
  sortedMsg = [c for _, c in frequencyAnalysis(message)]
  sortedAlp = [c for c in str(sortedAlphabet).decode('utf-8')
      if c in sortedMsg]

  factor = 0
  for i, c in enumerate(sortedMsg):
    factor += (i - sortedAlp.index(c)) ** 2

  return factor

def translateSubstrings(message, alphabet, sortedAlphabet, keyLenght):
  interpolated = []
  for idx in xrange(keyLenght):
    interpolatedMessage = message[idx::keyLenght]
    freqs = {}
    for c in str(alphabet).decode('utf-8'):
      freqs[c] = interpolatedMessage.count(c)
    freqs = [(n, c) for c, n in freqs.iteritems()]
    freqs.sort()
    freqs.reverse()
    majorLetters = [x[1] for x in freqs]
    interpolatedMessage = ''.join([(c in majorLetters) and c or '_' for
      c in interpolatedMessage])
    transtable = {'_': '_'}
    for orig, new in zip(majorLetters, str(sortedAlphabet).decode('utf-8')):
      transtable[orig] = new
    interpolatedMessage = map(lambda c: transtable[c], interpolatedMessage)
    interpolated.append(interpolatedMessage)
    # print ''.join([transtable[c] for c in str(alphabet).decode('utf-8')])
    # print [c for c in transtable.keys() if transtable[c] == ' '][0],
  return ''.join([''.join(x) for x in zip(*interpolated)])

def averageFriedmanTest(message, alphabet, keyLenght):
  Cis = []
  for idx in xrange(keyLenght):
    interpolatedMessage = message[idx::keyLenght]
    Ci, _ = friedmanTest(interpolatedMessage, alphabet)
    Cis.append(Ci)
  averageCi = sum(Cis) / len(Cis)
  return averageCi

def friedmanTest(message, alphabet):
  if not isinstance(message, unicode):
    raise AnalysisError, 'Message must be a unicode string'

  Kr = 1.0 / 28 # XXX: For 26 letters (really 28)
  Kp = 0.067 # XXX: For monocase english without ñ and _
  Ko = 0.0
  messageLen = 0
  for c in str(alphabet).decode('utf-8'):
    n = message.count(c)
    Ko += n * (n - 1)
    messageLen += n
  Ko /= messageLen * (messageLen - 1)
  Ci = int((Kp - Kr) / (Ko - Kr))
  return Ko, Ci

def kasiskiExamination(message, maxLength=5):
  if not isinstance(message, unicode):
    raise AnalysisError, 'Message must be a unicode string'

  freqs = {}
  for length in xrange(3, maxLength + 1): # Length range from 2 to maxLength
    print length
    for idx in xrange(len(message) - length):
      pattern = message[idx:idx+length]
      if pattern not in freqs:
        patternIdx = []
        jdx = message.find(pattern)
        while jdx >= 0:
          patternIdx.append(jdx)
          jdx = message.find(pattern, jdx + 1)
        diffIdx = []
        for i, j in zip(patternIdx[:-1], patternIdx[1:]):
          diffIdx.append(j - i)
        if diffIdx:
          freqs[pattern] = diffIdx
  for k, v in freqs.iteritems():
    print k, ':', v


def frequencyAnalysis(elements, sortResult=True, reverseResult=True):
  lengthSet = set(map(len, elements))
  if len(lengthSet) > 1:
    raise AnalysisError, 'All elements must be of the same length'

  frecuencies = {}
  for element in elements:
    frecuencies[element] = frecuencies.get(element, 0) + 1
  
  aux = [(v, k) for k, v in frecuencies.iteritems()]
  if sortResult:
    aux.sort()
  if reverseResult:
    aux.reverse()
  return aux

def prettyPrint(results, subElementAlphabet, out=sys.stdout):
  lengthSet = set(map(lambda x: len(x[1]), results))
  if len(lengthSet) > 1:
    raise AnalysisError, 'All elements must be of the same length'
  elementsLength = list(lengthSet)[0]

  resultsDict = {}
  for v, k in results:
    resultsDict[k] = v

  if elementsLength == 1: # 1D print
    maximum = max(resultsDict.values())
    step = 5
    for i in xrange(maximum, 0, -1):
      print >> out, i % step and '   ' or ('%3d' % i),
      for column in str(subElementAlphabet):
        print >> out, (resultsDict.get(column, 0) >= i) and (i % step and '*' or column) or ' ',
      print >> out
    print >> out, '    ' + ' '.join(str(subElementAlphabet))

  elif elementsLength == 2: # 2D print
    divisor = 18 * '-'
    divisor = '+-' + '+-'.join([divisor] * (len(str(subElementAlphabet)) / 6)) + '+--'
    totalColumn = len(str(subElementAlphabet)) * [0]
    for i, row in enumerate(str(subElementAlphabet)):
      if not i % 6:
        print >> out, divisor
      print >> out, '|',
      totalRow = 0
      for j, column in enumerate(str(subElementAlphabet)):
        if j and not j % 6:
          print >> out, '|',
        value = resultsDict.get(u'%s%s' % (row, column), 0)
        totalRow += value
        totalColumn[j] += value
        value = value and ('%2d' % value) or '  '
        print >> out, value,
      print >> out, '|',
      print >> out, row, totalRow
    print >> out, divisor
    print >> out, ' ',
    for i, c in enumerate(str(subElementAlphabet)):
      if i and not i % 6:
        print >> out, '|',
      print >> out, '%2s' % c,
    print >> out, '|'
    for i, value in enumerate(totalColumn):
      if i and not i % 6:
        print >> out, ' ',
      if not i % 2:
        print >> out, '%4d ' % value,
    print
    print '  ',
    for i, value in enumerate(totalColumn):
      if i and not i % 6:
        print >> out, ' ',
      if i % 2:
        print >> out, '%4d ' % value,

  else:
    raise AnalysisError, 'Unable to print elements of length larger than 2'

